COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input acphdr % Section 3.6
C00003 00003	%folio 223 galley 1E (C) Addison-Wesley 1978	*
C00019 00004	%folio 229 galley 2E NOTE:Middle and end clobbered. (C) Addison-Wesley 1978	*
C00036 00005	\vfill\eject
C00037 ENDMK
C⊗;
\input acphdr % Section 3.6
\runninglefthead{RANDOM NUMBERS} % chapter title
\titlepage\setcount00
\vfill
\tenpoint
\ctrline{SECTION 3.6 of THE ART OF COMPUTER PROGRAMMING}
\ctrline{$\copyright$ 1978 Addison--Wesley Publishing Company, Inc.}
\vfill
\runningrighthead{SUMMARY}
\section{3.6}
\eject
\setcount0 169
%folio 223 galley 1E (C) Addison-Wesley 1978	*
\sectionbegin{3.6. SUMMARY}
W{\:cE HAVE COVERED} a fairly large number of topics
in this chapter: how to generate random numbers, how to test
them, how to modify them in applications, and how to derive
theoretical facts about them. Perhaps the main question in many
readers' minds will be, ``What is the result of all this theory?
What is a simple, virtuous generator I can use
in my programs in order to have a reliable source of random
numbers?''

The detailed investigations in this chapter suggest
that the following procedure gives the ``nicest'' and ``simplest''
random-number generator for the machine language of must computers:
At the beginning of the program, set an integer variable $X$
to some value $X↓0$. This variable $X$ is to be used only for
the purpose of random-number generation. Whenever a new random
number is required by the program, set
$$X ← (aX + c)\mod m\eqno (1)$$
and use the new value of $X$ as the random value.
It is necessary to choose $X↓0$, $a$, $c$, and $m$ properly, and
to use the random numbers wisely, according to the following
principles:

\yyskip\textindent{i)}\hang The ``seed'' number $X↓0$ may be chosen
arbitrarily. If the program is run several times and a different
source of random numbers is desired each time, set $X↓0$ to
the last value attained by $X$ on the preceding run; or (if
more convenient) set $X↓0$ to the current date and time. If
the program may need to be rerun later with the {\sl same} random
numbers (e.g., when debugging), be sure to print out $X↓0$ if
it isn't otherwise known.

\yskip\textindent{ii)}\hang The number $m$ should be large, say
at least $2↑{30}$. It may conveniently be taken as the computer's
word size, since this makes the computation of $(aX + c)\mod
m$ quite efficient. Section 3.2.1.1 discusses the choice of $m$
in more detail. The computation of $(aX + c)\mod m$ must be
done {\sl exactly}, with no roundoff error.

\yskip\textindent{iii)}\hang If $m$ is a power of 2 (i.e., if a
binary computer is being used), pick $a$ so that $a \mod 8 =
5$. If $m$ is a power of 10 (i.e., if a decimal computer is being
used), choose $a$ so that $a \mod 200 = 21$. This choice of $a$
together with the choice of $c$ given below ensures that the
random-number generator will produce all $m$ different possible
values of $X$ before it starts to repeat (see Section 3.2.1.2)
and ensures high ``potency'' (see Section 3.2.1.3).

\yskip\textindent{iv)}\hang The multiplier $a$ should preferably
be chosen between .01$m$ and .99$m$, and its binary or decimal
digits should {\sl not} have a simple, regular pattern. By choosing
some haphazard constant like $a = 3141592621$ $\biglp$which satisfies
both of the conditions in (iii)$\bigrp$, one almost always obtains
a reasonably good multiplier. Further testing should of course
be done if the random-number generator is to be used extensively;
for example, there should be no large quotients when Euclid's
algorithm is used to find the gcd of $a$ and $m$ (see Section
3.3.3). The multiplier should pass the spectral test (Section
3.3.4) and several tests of Section 3.3.2, before it is considered
to have a truly clean bill of health.

\yskip\textindent{v)}\hang The value of $c$ is immaterial when $a$
is a good multiplier, except that $c$ must have no factor in
common with $m$. Thus we may choose $c = 1$ or $c = a$.

\yskip\textindent{vi)}\hang The least significant (right-hand) digits
of $X$ are not very random, so decisions based on the number
$X$ should always be influenced primarily by the most significant
digits. It is generally best to think of $X$ as a random fraction
$X/m$ between 0 and 1, that is, to visualize $X$ with a decimal
point at its left, rather than to regard $X$ as a random integer between
0 and $m - 1$. To compute a random integer between 0 and $k
- 1$, one should multiply by $k$ and truncate the result (see
the beginning of Section 3.4.2).

\yskip\textindent{vii)}\hang An important limitation on the randomness
of sequence (1) is discussed in Section 3.3.4, where it is shown
that the ``accuracy'' in $t$ dimensions will be only about one
part in $\raise 3pt\hjust to 0pt{\hskip
3pt minus 20pt\:lt\hskip 0pt minus 10000pt}\sqrt{m}$. % t-th root
Monte Carlo applications requiring higher
resolution can improve the randomness by employing techniques
discussed in Section 3.2.2.

\yyskip The above comments apply primarily to machine-language
coding. In higher-level programming languages, we are often
unable to use such machine-dependent features as integer arithmetic
modulo the word size, and careful compilers will not allow us
to compute the product of two large integers. Another technique
which we might call the {\sl subtractive method} (exercise 3.2.2--23)
can be used to provide a ``portable'' random-number generator
which is efficiently describable in any higher-level programming
language, since it makes use only of integer arithmetic between
$-10↑9$ and $+10↑9$. Here is how the subtractive method might be
coded in FORTRAN, as a subroutine that delivers an array of
55 random integers at once:
\def\\{\ \ \ \ \ \ }
$$\halign to size{\tt #\hfill\cr
\\FUNCTION IRN55(IA)\cr
\\DIMENSION IA(1)\cr
C\ \ \ \ \ ASSUMING THAT IA(1), ..., IA(55) HAVE BEEN\cr
C\ \ \ \ \ SET UP PROPERLY, THIS SUBROUTINE RESETS THE IA ARRAY\cr
C\ \ \ \ \ TO THE NEXT 55 NUMBERS OF A PSEUDO-RANDOM SEQUENCE,\cr
C\ \ \ \ \ AND RETURNS THE VALUE 1.\cr
\\DO 1 I = 1, 24\cr
\\\ \ J = IA(I) - IA(I+31)\cr
\\\ \ IF (J .LT. 0) J = J + 1000000000\cr
\\\ \ IA(I) = J\cr
\ \ 1\ \ \ CONTINUE\cr
\\DO 2 I = 25, 55\cr
\\\ \ J = IA(I) - IA(I-24)\cr
\\\ \ IF (J .LT. 0) J = J + 1000000000\cr
\\\ \ IA(I) = J\cr
\ \ 2\ \ \ CONTINUE\cr
\\IRN55=1\cr
\\RETURN\cr
\\END\cr}$$
To use these numbers in a FORTRAN program,
let {\tt JRAND} be an auxiliary integer variable; we may obtain the
next random number {\tt U} (as a fraction between 0 and 1) by writing
the following three statements:
$$\halign to size{\tt #\hfill\cr
\\JRAND = JRAND + 1\cr
\\IF (JRAND .GT. 55) JRAND = IRN55(IA)\cr
\\U = FLOAT(IA(JRAND)) * 1.0E-9\cr}$$
At the beginning of our program we need to write
``{\tt DIMENSION IA(55)}'' and ``{\tt JRAND=55}'' and we must also initialize
the {\tt IA} array. Appropriate initialization can be done by calling
the following subroutine with {\tt IX} set to any integer value (selected
like $X↓0$ in rule (i) above, preferably large):
$$\halign to size{\tt #\hfill\cr
\\SUBROUTINE IN55(IA,IX)\cr
\\DIMENSION IA(1)\cr
C\ \ \ \ \ THIS SUBROUTINE SETS IA(1), ..., IA(55) TO STARTING\cr
C\ \ \ \ \ VALUES SUITABLE FOR LATER CALLS ON IRN55(IA).\cr
C\ \ \ \ \ IX IS AN INTEGER "SEED" VALUE BETWEEN 0 AND 999999999.\cr
\\IA(55) = IX\cr
\\J = IX\cr
\\K = 1\cr
\\DO 1 I = 1, 54\cr
\\\ \ II = MOD(21*I, 55)\cr
\\\ \ IA(II) = K\cr
\\\ \ K = J - K\cr
\\\ \ IF (K .LT. 0) K = K + 1000000000\cr
\\\ \ J = IA(II)\cr
\ \ 1\ \ \ CONTINUE\cr
C\ \ \ \ \ THE NEXT THREE LINES "WARM UP" THE GENERATOR\cr
\\IRN55(IA)\cr
\\IRN55(IA)\cr
\\IRN55(IA)\cr
\\RETURN\cr
\\END\cr}$$
$\biglp$This subroutine computes a Fibonacci-like
sequence; multiplication of indices by 21 spreads the values
around so as to alleviate initial nonrandomness problems such
as those in exercise 3.2.2--2. Note that $2↑{29} < 10↑9 < 2↑{30}$;
any large even number may actually be substituted for $10↑9$ in
these routines, if a corresponding change is made in the computation
of the random fraction {\tt U}. Furthermore it would be possible
to work directly with floating-point numbers instead of integers by
making appropriate changes to these programs, {\sl provided} that the
computer's floating-point arithmetic is sufficiently accurate to give
{\sl exact} results in all the computations required here. Most binary
computers will be able to meet this requirement when all of the numbers to be
dealt with have the form $a/2↑p$, where $a$ is an integer, $0≤a<2↑p$, and
there are $p$ bits of precision in floating-point fractions.
The numbers $(24, 55)$ in these routines may be replaced
by any pair of values $(j, k)$ in Table 3.2.2--1, for $k ≥ 50$;
the constants 31, 25, 54, 21 should then be replaced by $k -
j$, $j + 1$, $k - 1$, and $d$ respectively, where $d$ is relatively
prime to $k$ and $d \approx k/\phi ↑2$.$\bigrp$

Although a great deal is known about linear congruential
sequences like (1), very little has yet been proved about the
randomness properties of the subtractive method. Both approaches
seem to be reliable in practice.

Unfortunately, quite a bit of published material
in existence at the time this chapter was written recommends
the use of generators which violate the suggestions above; and
the most common generator in actual use, {\tt RANDU}, is really horrible
(cf.\ Section 3.3.4). The authors of many contributions to the
science of random-number generation were unaware that particular
methods they were advocating would prove to be inadequate.
Perhaps further research will show that even the random-number generators
recommended here are unsatisfactory; we hope this is not the case, but
the history of the subject warns us to be cautious. The most prudent
policy for a person to follow is to run each Monte Carlo program at least
twice using quite different sources of random numbers, before taking
the answers of the program seriously; this not only will give an indication
of the stability of the results, it also will guard against the danger
of trusting in a generator with hidden deficiencies. (Every random-number
generator will fail in at least one application.)
%folio 229 galley 2E NOTE:Middle and end clobbered. (C) Addison-Wesley 1978	*
\yskip Excellent bibliographies of the pre-1972
literature on random-number generation have been compiled by
Richard E. Nance and Claude Overstreet, Jr., {\sl Computing
Reviews \bf 13} (1972), 495--508, and by E. R. Sowey, {\sl International
Stat.\ Review \bf 40} (1972), 355--371. For further study, especially
with respect to {\sl a priori} theoretical tests, see the forthcoming book
{\sl Uniform Random Numbers} by U. Dieter and J. H. Ahrens.

For a detailed study of the use of random numbers
in numerical analysis, see J. M. Hammersley and D. C. Handscomb,
{\sl Monte Carlo Methods} (London: Methuen, 1964). This book
shows that some numerical methods are enhanced by using numbers
which are ``quasirandom,'' designed specifically for a certain
purpose (not necessarily satisfying the statistical tests we
have discussed).

Every reader is urged to work exercise 6 which follows.

\exbegin{EXERCISES}

\exno 1. [21] Write a \MIX\ subroutine
with the following characteristics, using method (1):
$$\eqalign{\hjust{Calling sequence:\qquad}⊗\hjust{\tt JMP RANDI}\cr
\noalign{\vskip 2pt}
\hjust{Entry conditions:\qquad}⊗\hjust{$\rA = k$, a positive integer
$< 5000$.}\cr
\noalign{\vskip 2pt}
\hjust{Exit conditions:\qquad}⊗\hjust{$\rA ←$ a random integer $Y$, $1 ≤
Y ≤ k$, with each integer}\cr
⊗\hjust{\qquad equally probable; $\rX = ?$; overflow toggle
unaffected.}\cr}$$

\trexno 2. [15] Some people have been afraid that computers will someday
take over the world; but they are reassured by the statement
that a machine cannot do anything really new, since it is only
obeying the commands of its master, the programmer. Lady Lovelace
wrote in 1844, ``The Analytical Engine has no pretensions to
{\sl originate} anything. It can do {\sl whatever we know how
to order it} to perform.'' Her statement has been further elaborated
by many philosophers. Discuss this topic, with random-number
generators in mind.

\exno 3. [32] ({\sl A dice game.})\xskip Write a program that simulates
a roll of two dice, each of which takes on the values 1, 2,
$\ldotss$, 6 with equal probability. If the total is 7 or 11 on
the first roll, the game is won; a total of 2, 3, or 12 loses;
and on any other total, call that total the ``point'' and continue
rolling dice until either a 7 occurs (a loss) or the point occurs
again (a win).

Play ten games. The result of each roll of the
dice should be printed in the form $m\;n$, where $m$ and $n$ are
the contents of the two dice, followed by some appropriate comment
(like ``snake eyes'' or ``little Joe'' or ``the hard way'',
etc.)

\exno 4. [40] ({\sl Solitaire or patience.})\xskip Some people spend a lot
of valuable time playing card games of solitaire, and perhaps
automation will make an important inroad in this area. Write
a program that\xskip (a) shuffles a simulated deck of cards;\xskip (b) plays
some common game of solitaire based on the order of the cards
in the deck;\xskip (c) prints out the result of the game, i.e., how
close the program came to winning. Several games should be played.
The program might be set up to ``cheat'' upon request.

\exno 5. [46] ({\sl Creative writing by computer.})\xskip A television program
entitled ``The Thinking Machine,'' broadcast by the CBS television
network on October 26, 1960, featured (among other things) two
Western-style playlets that were written by a computer program.
Here are the two scripts as they were printed out by the computer:

{\baselineskip 9pt \:>  % sans serif 8 on 9
\def\s:{\penalty-100 \vskip2pt \noindent
\hjust to 15mm{SHERIFF:\hfill}\hangindent15mm}
\def\r:{\penalty-100 \vskip2pt \noindent
\hjust to 15mm{ROBBER:\hfill}\hangindent15mm}
\vskip 6pt plus 3pt minus 4pt
\noindent {\:? Saga} {\:w\char'161}1. (The gun is
in the right hand; the money is in the left hand; the glass
is on the table; the bottle is on the table; the holster is
on the robber; the sheriff's gun is in the sheriff's right hand;
the sheriff's holster is on the sheriff.)

\r:(The robber is at the window.)
Go to door; open door; go thru door; close door; go to corner;
put money down at corner; go to table; put gun on table; sit
and fidgit; sit at table; pick up glass with right hand (empty);
put glass on table; pick up bottle with right hand; pour; put
bottle on table; pick up glass with right hand; take a drink
from glass; put glass on table; pick up bottle with right hand;
sit at table; sit at table; go to corner; go to window; go to table;
put bottle on table; sit and fidgit; sit at table; sit and fidgit;
go to window; go to table; pick up glass with right hand.

\s:(The sheriff is at the window.) See robber; (robber sees sheriff); go to
door.

\r:Put glass on table; pick up gun
with right hand; check gun.

\s:Wait; open door; see robber; (robber
sees sheriff); go thru door.

\r:Go to window; aim; fire; SHERIFF NICKED.

\s:Go to window; aim; fire; MISSED; go to door; go to window.

\r:Go to door; aim; aim.

\s:Aim; fire; MISSED.

\r:Fire; SHERIFF NICKED.

\s:Go to door; aim; fire; MISSED; go thru door; aim.

\r:Aim; fire; MISSED; aim; fire; MISSED.

\s:Fire; MISSED; go to window; aim; fire; MISSED.

\r:Aim; fire; MISSED; aim; fire; MISSED; aim; fire; SHERIFF NICKED.

\s:Aim; fire; ROBBER HIT.

\r:Drop gun; robber dies.

\s:Put gun in holster; go to table; pick up glass with right hand (empty);
take glass from right hand with left hand; pick up bottle with right hand;
pour; put bottle on table; take glass from left hand with right hand; take
a drink from glass; take glass from right hand with left hand; pick up bottle with
right hand; pour; put bottle on table; take
glass from left hand with right hand; take
a drink from glass; put glass on table; go to corner; pick up money
with right hand; go to door; go thru door; close door. CURTAIN.

\topinsert{\vskip 66mm} % room for the cartoon
\yyskip \noindent {\:? Saga} {\:w\char'161}2. (The gun is in the right
hand; the money is in the left hand; the glass is on the table;
the bottle is on the table; the holster is on the robber; the
sheriff's gun is in the sheriff's right hand; the sheriff's
holster is on the sheriff.)

\r:(The robber is at the window.)
Go to door; open door; go thru door; close door; go to corner;
put money down at corner; go to window; put gun down at window;
lean on window and look; lean on window and look; go to corner;
count money; go to table; pick up glass with right hand (empty);
take glass from right hand with left hand; pick up bottle with
right hand; pour; put bottle on table; take glass from left
hand with right hand; take a drink from glass; put glass on
table; pick up bottle with right hand; pour; go to corner; put
bottle down at corner; go to window; pick up gun with right
hand; check gun; put gun in holster; go to table; pick up glass
with right hand; take a drink from glass; go to window; put glass
down at window.

\s:(The sheriff is at the window.) See robber; (robber sees sheriff);
go to door.

\r:Take gun from holster with right hand; check gun; go to door; check gun;
put gun down at door.

\s:Open door; see robber; (robber sees sheriff); go thru door; go to window.

\r:Pick up gun with right hand.

\s:Go to table.

\r:Aim; fire; MISSED; aim; fire; SHERIFF HIT; blow out barrel; put gun in
holster.

\s:Drop gun; sheriff dies.

\r:Go to corner; pick up money with right hand; go to door; go thru door;
close door. CURTAIN.

\penalty-300\vskip 6pt plus 3pt minus 4pt}
A careful reading of the above scripts reveals the highly intense drama
present here. The computer program was careful to keep track of the locations
of each player, the contents of his hands, etc. Actions taken by the players
were random, governed by certain probabilities; the probability of a foolish
action was increased depending on how much that player had had to drink and
on how often he had been nicked in a shot. The reader will be able to deduce
further properties of the program by studying the sample scripts.

Of course, even the best scripts are rewritten before they are produced, and
this is especially true when an inexperienced writer has prepared the original
draft. Here are the scripts just as they were actually used in the show:

{\baselineskip 10pt \:>
\vskip 6pt plus 3pt minus 4pt
\halign{#\hfill\quad⊗#\hfill\cr
\noalign{\hjust{\:?Saga \:w\char'161\:>1.\quad Music up.}}
MS⊗Robber peering thru window of shack.\cr
CU⊗Robber's face.\cr
MS⊗Robber entering shack.\cr
CU⊗Robber sees whiskey bottle on table.\cr
CU⊗Sheriff outside shack.\cr
MS⊗Robber sees sheriff.\cr
LS⊗Sheriff in doorway over shoulder of robber, both draw.\cr
MS⊗Sheriff drawing gun.\cr
LS⊗Shooting it out. Robber gets shot.\cr
MS⊗Sheriff picking up money bags.\cr
MS⊗Robber staggering.\cr
MS⊗Robber dying. Falls across table, after trying to take last shot at sheriff.\cr
MS⊗Sheriff walking thru doorway with money.\cr
MS⊗of robber's body, now still, lying across table top. Camera dollies back.
(Laughter)\cr
\noalign{\yskip\hjust{\:?Saga \:w\char'161\:>2.\quad Music up.}}
CU⊗of window. Robber appears.\cr
MS⊗Robber entering shack with two sacks of money.\cr
MS⊗Robber puts money bags on barrel.\cr
CU⊗Robber---sees whiskey on table.\cr
MS⊗Robber pouring himself a drink at table. Goes to count money. Laughs.\cr
MS⊗Sheriff outside shack.\cr
MS⊗thru window.\cr
MS⊗Robber sees sheriff thru window.\cr
LS⊗Sheriff entering shack. Draw. Shoot it out.\cr
CU⊗Sheriff. Writhing from shot.\cr
\noalign{\hjust{M/2 shot\quad Sheriff staggering to table for a drink . . .
falls dead.}}
MS⊗Robber leaves shack with money bags.*\cr}}
\botinsert{\hrule width 5pc\vskip 3pt \baselineskip 9pt
\hjust to size{\eightpoint*$\copyright$ 1962 by Columbia Broadcasting System,
Inc. All Rights Reserved. Used by permission. For further information, see
J. E. Pfeiffer, {\sl The Thinking Machine} (New York: J. B. Lippincott, 1962).}}
\vskip 6pt plus 3pt minus 4pt
[{\sl Note:} CU = ``close up'', MS = ``medium shot'', etc. The above details
were kindly furnished to the author by Thomas H. Wolf, producer of the
television show, who suggested the idea of a computer-written playlet in the first
place, and also by Douglas T. Ross and Harrison R. Morse who produced the
computer program.]

The reader will undoubtedly have many ideas about how he could prepare his own
computer program to do creative writing; and that is the point of this
exercise.

\trexno 6. [40] Look at the subroutine library of each computer installation
in your organization, and replace the random-number generators by good ones.
Try to avoid being too shocked at what you find.
\vfill\eject